class Solution
{
public:
    int countDifferentSubsequenceGCDs(vector<int> &nums)
    {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int maxNum = *max_element(nums.begin(), nums.end());
        int count = 0;
        for (int i = 1; i <= maxNum; ++i)
        {
            int subGcd = -1;
            for (int x = i; x <= maxNum; x += i)
            {
                if (numSet.count(x))
                {
                    if (subGcd == -1)
                    {
                        subGcd = x;
                    }
                    else
                    {
                        subGcd = gcd(subGcd, x);
                    }
                    if (subGcd == i)
                    {
                        break;
                    }
                }
            }
            if (subGcd == i)
            {
                ++count;
            }
        }
        return count;
    }
};